package org.alg.graph;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;

/**
 * Created by sunlei on 2015/5/2.
 * 使用深度优先搜索找出图中的所有连通分量
 */
public class CC {
    private boolean[] marked;
    private int[] id;
    private int count;

    public CC(Graph G){
        marked=new boolean[G.V()];
        id=new int[G.V()];
        for(int s=0;s<G.V();s++){
            if(!marked[s]) {
                dfs(G, s);
                count++;
            }
        }
    }

    private void dfs(Graph G,int v){
        marked[v]=true;
        id[v]=count;
        for(int w:G.adj(v)){
            if(!marked[w])
                dfs(G,w);
        }
    }

    public boolean connected(int v,int w){
        return id[v]==id[w];
    }

    public int id(int v){
        return id[v];
    }

    public int count(){
        return count;
    }

    public static void main(String[] args) throws IOException {
        File f=new File("D:\\arg-data\\tinyG.txt");
        FileInputStream fis=new FileInputStream(f);
        Graph graph=new Graph(fis);
        CC cc=new CC(graph);
        for(int i=0;i<graph.V();i++){
            if(cc.id(i)==0)
                System.out.println(i);
        }
    }
}
